"""
超时。。。
"""
from typing import List
from collections import defaultdict, deque
class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        if endWord not in wordList:
            return []
        L = len(beginWord)
        all_combo_dict = defaultdict(list)
        for word in wordList:
            for i in range(L):
                all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)
        
        print(all_combo_dict)
        d = deque() # 存放单词
        d.append( [beginWord])
        ans = []
        find_flag = None

        while d: # 循环双端列表
            word_record = d.pop()
            last_word = word_record[-1]
            if find_flag and len(word_record) != find_flag:
                break
            for i in range(L):
                combo_word = last_word[:i] + "*" + last_word[i+1:]
                words = all_combo_dict.get(combo_word, [])
                for word in words:
                    if word not in word_record:
                        record_copy = word_record.copy()
                        record_copy.append(word)
                        if word == endWord:
                            # 找到之后, 把这一层的循环完毕就不找了
                            ans.append(record_copy)
                            find_flag = len(record_copy) - 1
                        else:
                            d.appendleft(record_copy)
        return ans

def test():
    assert Solution().findLadders("hit", "cog", ["hot","dot","dog","lot","log"])== []

def test1():
    assert Solution().findLadders("hit", "cog", ["dot","dog","lot","log", "cog"])== []

if __name__ == "__main__":
    r = Solution().findLadders("hit", "cog", ["hot","dot","dog","lot","log","cog"])
    # r = Solution().ladderLength("hot", "dog", ["hot","dog"])
    print(r)
